package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 20.有效的括号
 *
 * @program: LeetCode->LeetCode_20
 * @description: 20.有效的括号
 * @author: cg
 * @create: 2021-09-03 22:12
 **/
public class LeetCode_20 {

    @Test
    public void test20() {
        System.out.println(isValid("("));
        System.out.println(isValid(")"));
        System.out.println(isValid("()"));
        System.out.println(isValid("{[]}"));
        System.out.println(isValid("{[]}[]()"));
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：
     * 1) 左括号必须用相同类型的右括号闭合。
     * 2) 左括号必须以正确的顺序闭合。
     * <p>
     * 示例 1：
     * 输入：s = "()"
     * 输出：true
     * <p>
     * 示例 2：
     * 输入：s = "()[]{}"
     * 输出：true
     * <p>
     * 示例 3：
     * 输入：s = "(]"
     * 输出：false
     * <p>
     * 示例 4：
     * 输入：s = "([)]"
     * 输出：false
     * <p>
     * 示例 5：
     * 输入：s = "{[]}"
     * 输出：true
     * <p>
     * 提示：
     * 1) 1 <= s.length <= 10的4次幂
     * 2) s 仅由括号 '()[]{}' 组成
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> lstack = new Stack();
        for (char ch : s.toCharArray()) {
            switch (ch) {
                case '(':
                case '[':
                case '{':
                    lstack.push(ch);
                    break;
                case ')':
                    if (lstack.size() != 0 && lstack.peek() == ch - 1) {
                        lstack.pop();
                    } else {
                        return false;
                    }
                    break;
                case ']':
                case '}':
                    if (lstack.size() != 0 && lstack.peek() == ch - 2) {
                        lstack.pop();
                    } else {
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        return lstack.size() == 0;
    }

}
